Misja kosmiczna

Limit pamięci: 128 MB

Bajtocja szykuje się do wystrzelenia pierwszej rakiety w kosmos. Bajtazar jest jednym z pracowników programu kosmicznego i odpowiada za proces wsiadania astronautów do rakiety. Wnętrze rakiety składa się z kajut połączonych dwukierunkowymi korytarzami w taki sposób, że pomiędzy każdymi dwiema kajutami można przejść na dokładnie jeden sposób (jeśli nie będziemy po drodze zawracać). Przejście każdego korytarza zajmuje jedną sekundę bajtocką. Kajuty są ponumerowane od do . Wejście do rakiety prowadzi do kajuty numer .

Do rakiety wsiadać będzie kosmonautów, również ponumerowanych od do . Dla każdego kosmonauta numer mieszkać będzie w kajucie numer . Kosmonauci wchodzą do rakiety jeden po drugim w odstępach jednosekundowych (w sekundach bajtockich) i idą najkrótszą drogą do swojej kajuty. Kosmonauta numer po dotarciu do swojej kajuty zaczyna rozkładać swoje rzeczy, co zajmuje mu dokładnie sekund bajtockich.

Kolejność wchodzenia mieszkańców na statek musi być taka, by nikt nie musiał przechodzić przez kajutę, w której znajduje się już jej mieszkaniec (niezależnie od tego, czy ów mieszkaniec zakończył już rozpakowywanie, czy jeszcze nie).

Zadaniem Bajtazara jest takie zaplanowanie procesu wsiadania do rakiety, by przebiegł on jak najszybciej, to znaczy by pomiędzy wejściem pierwszego kosmonauty na statek a momentem, w którym wszyscy kosmonauci zakończą rozpakowywanie, upłynęło jak najmniej czasu.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita () oznaczająca liczbę kosmonautów i liczbę kajut. Drugi wiersz zawiera ciąg liczb całkowitych (). Liczba określa, ile czasu potrzebuje kosmonauta numer na rozpakowanie się. Kolejne wierszy opisuje układ kajut na statku. Każdy z nich zawiera dwie liczby całkowite i (), które oznaczają, że kajuty o numerach i są połączone bezpośrednim korytarzem.

Wyjście

Wypisz minimalny czas potrzebny wszystkim kosmonautom na wejście na statek i rozlokowanie się w kajutach.

Przykład

Dla danych wejściowych:

5
2 3 5 2 1
2 1
3 2
2 4
1 5

poprawną odpowiedzią jest:

7

Autor zadania: Jakub Łącki.